import common.TreeNode;

/**
 * 124. Binary Tree Maximum Path Sum 最大路径和
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 */
class BinaryTreeMaximumPathSum {

    int ans = Integer.MIN_VALUE;

    /**
     * 方法：maxPathSum 使用DFS计算二叉树中的最大路径和
     * 
     * Args:
     *   root (TreeNode): 二叉树的根节点
     * 
     * Returns:
     *   int: 二叉树中任意路径的最大路径和
     * 
     * Time:
     *   O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
     * 
     * Space:
     *   O(H)，其中 H 为二叉树的高度。递归调用的栈空间取决于二叉树的高度。
     */
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node){
        if (node == null){
            return 0;
        }
        // 递归计算左右子节点的最大路径和
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int l_val = Math.max(dfs(node.left), 0);
        int r_val = Math.max(dfs(node.right), 0);

        ans = Math.max(ans, l_val + r_val + node.val);
        return Math.max(l_val, r_val) + node.val;
    }
}